//
// Created by shenbin on 2022/5/22.
// https://leetcode.cn/problems/merge-k-sorted-lists/
//

#ifndef ALGORITHM_TRAINNING_C06_LC23_H
#define ALGORITHM_TRAINNING_C06_LC23_H

#include <vector>
#include <queue>

using namespace std;


struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int _val) : val(_val), next(nullptr) {}

    ListNode(int _val, ListNode *_next) : val(_val), next(_next) {}

};

struct Node {
    int key;
    ListNode *listNode;

    Node() : key(0), listNode(nullptr) {}

    Node(int _key) : key(_key), listNode(nullptr) {}

    Node(int _key, ListNode *_listNode) : key(_key), listNode(_listNode) {}
};

bool operator<(const Node &a, const Node &b) {
    return a.key > b.key;
}

class LeetCode23PriorityQueue {
public:


    ListNode *mergeKLists(vector<ListNode *> &lists) {
        for (ListNode *listNode: lists) {
            if (listNode == nullptr) continue;
            q.push(Node(listNode->val, listNode));
        }
        ListNode head;
        ListNode *tail = &head;
        while (!q.empty()) {
            Node node = q.top();
            q.pop();
            tail->next = node.listNode;
            tail = tail->next;
            ListNode *next = node.listNode->next;
            if (next != nullptr)
                q.push(next->val, next);
        }
        return head.next;

    }


private:
    priority_queue<Node> q;
};

class BinaryHeap{
public:
    bool empty(){
        return heap.size() == 1;
    }




private:
    vector<Node> heap;
};

class LeetCode23BinaryHeap {

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {

    }

private:

};

#endif //ALGORITHM_TRAINNING_C06_LC23_H
